#pragma once

#include <utility>

#include "PagedStorage.h"
#include "MyMap.h"

template <typename T>
class Hashtable : public IContainer<T>
{
public:
	typedef int (*Hasher) (T*);
	typedef int (*Comparator) (T*, T*);

	Hashtable(int, Hasher, Comparator);
	~Hashtable();

	virtual bool insert(T*);
	virtual T* find(T*);
	virtual void clear();

private:

	struct List
	{
		List* pNext;
		T* pData;

		List()
			: pNext(NULL)
			, pData(NULL)
		{}

		List(List* _pNext, T* _pData)
			: pNext(_pNext)
			, pData(_pData)
		{}
	};

	void resize(void);

	Hasher m_hasher;
	Comparator m_cmp;
	List** m_table;
	int m_table_len;
	PagedStorage<List> m_store;

	//static int[] SIZES = {11, 17, 29, 41, 59, 89, 137 , 211 , 307 , 457 , 683 , 1021 , 1531 , 2297
	//	, 3449 , 5167 , 7753 , 11633 , 17443 , 26153 , 39227 , 58889 };
};

template <typename T>
Hashtable<T>::Hashtable(int initLen, Hasher hasher, Comparator cmp)
	: m_table_len(initLen)
	, m_hasher(hasher)
	, m_cmp(cmp)
{
	m_table = new List*[m_table_len];
	for (int i=0; i < m_table_len; ++i)
		m_table[i] = NULL;
}

template <typename T>
Hashtable<T>::~Hashtable()
{
	delete[] m_table;
	m_store.free();
}

template <typename T>
bool
Hashtable<T>::insert(T* pT)
{
	int pos = m_hasher(pT) % m_table_len;
	for (List* it = m_table[pos]; it != NULL; it = it->pNext)
	{
		if (!m_cmp(it->pData, pT))
		{
			it->pData = pT;
			return false;
		}
	}

	List* list = m_store.allocate();
	list->pNext = m_table[pos];
	list->pData = pT;
	m_table[pos] = list;
	return true;
}

template <typename T>
T*
Hashtable<T>::find(T* pT)
{
	int pos = m_hasher(pT) % m_table_len;
	for (List* it = m_table[pos]; it != NULL; it = it->pNext)
	{
		if (!m_cmp(it->pData, pT))
		{
			return it->pData = pT;
		}
	}

	return NULL;
}

template <typename T>
void
Hashtable<T>::resize()
{
//	int m_table_len = 
}

template <typename T>
void
Hashtable<T>::clear()
{

}